namespace cpputils
{

struct randomizer : public virtual_object
{
	virtual int max_rand() const = 0;
	virtual void seed(int Val);
	virtual int operator()() = 0;
};

struct c_randomizer : public randomizer
{
	int max_rand() const;
	void seed(int Val);
	int operator()();
};

// Knuth's subtractive routine
struct knuth_randomizer : public randomizer
{
	knuth_randomizer();
	int max_rand() const;
	void seed(int Val);
	int operator()();

private:
	static const int MSEED, MBIG;

	int inext, inextp;
	long ma[56];
};

typedef knuth_randomizer std_randomizer;

c_randomizer& crand();
std_randomizer& stdrand();

int uniform(int N, randomizer& Rand = stdrand());
double uniform(randomizer& Rand = stdrand());
double gaussian(randomizer& Rand = stdrand());

template<class T>
void shuffle(T Begin, T End, randomizer& Rand = stdrand())
{
	shuffle_n(Begin, End, End, Rand);
}

template<class T>
void shuffle_n(T Begin, T Mid, T End, randomizer& Rand = stdrand())
{
	assert(Begin <= Mid && Mid <= End);
	for (int N = End - Begin; Begin < Mid; ++Begin, N--)
		swap(*Begin, *(Begin + uniform(N, Rand)));
}

template<class InT, class OutT>
void sample_n(InT Begin, InT End, OutT Out, int N, randomizer& Rand = stdrand())
{
	int Total = End - Begin;
	assert(Total >= N);
	for (; Begin != End; ++Begin, --Total)
		if (uniform(Total, Rand) < N) *Out = *Begin, ++Out, N--;
}

struct histogram_randomizer : public randomizer
{
public:
	void set_histogram(subarray<const double> Probs);
	subarray<const double> get_partial_sums() const;
	double get_partial_sum(int Min, int Max) const;
	int max_rand() const;
	int operator()();
	int operator()(int Min, int Max);

private:
	array<double> PSums;
};

}
